package com.kangkang.leetcode20;

import java.util.ArrayList;
import java.util.List;

public class Test120 {
}
class Solution120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();
        int[][] minPath= new int[row][triangle.get(row-1).size()];
        minPath[0][0] = triangle.get(0).get(0);
        int result = Integer.MAX_VALUE;
        if(row==1){
            return minPath[0][0];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 0; j <= i; j++) {

                if(j==0){
                    minPath[i][j] = minPath[i-1][j]+triangle.get(i).get(j);
                }else if (j==i){
                    minPath[i][j] = minPath[i-1][j-1]+triangle.get(i).get(j);
                }else {
                    minPath[i][j] = Math.min(minPath[i-1][j-1],minPath[i-1][j])+triangle.get(i).get(j);
                }
                if(i==row-1){
                    result = Math.min(result,minPath[i][j]);
                }
            }
        }
        return result;

    }
}